package com.zh.note.huawei.twohundred.区间交集;

import java.util.*;

/**
 * https://dream.blog.csdn.net/article/details/132600391
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<Interval> list = new ArrayList<>();

        while (sc.hasNextInt()) {
            int left = sc.nextInt();
            int right = sc.nextInt();
            list.add(new Interval(left, right));
        }

        //按照区间开始位置排序
        Collections.sort(list, (o1, o2) -> o1.start - o1.start);
        Interval[] combinedIntervals = new Interval[100];
        int index = 0;
        int right = -1;
        //1、 模拟求出所有公共区间
        for (int i = 0; i < list.size(); i++) {
            Interval interval = list.get(i);
            if (interval.end < right) {
                continue;
            }
            right = interval.end;
            for (int j = i + 1; j < list.size(); j++) {
                Interval nextInterval = list.get(j);
                if (interval.end < nextInterval.start) {
                    break;
                } else if (interval.end == nextInterval.start) {
                    combinedIntervals[index++] = new Interval(interval.end, interval.end);
                    break;
                } else {
                    int minEnd = Math.min(interval.end, nextInterval.end);
                    combinedIntervals[index++] = new Interval(nextInterval.start, minEnd);
                }
            }
        }
        if (index == 0) {
            System.out.println("None");
            return;
        }

        Interval[] temp = Arrays.copyOf(combinedIntervals, index);
        Interval[] result = mergerIntervals(temp);
        for (Interval interval : result) {
            System.out.println(interval.start + " " + interval.end);
        }
    }

    // 2、合并重叠区间
    private static Interval[] mergerIntervals(Interval[] intervals) {
        List<Interval> mergedList = new ArrayList<>();
        int index = 0;
        for (int i = 0; i < intervals.length; i++) {
            Interval interval = intervals[i];
            if (index == 0 || interval.start > mergedList.get(index - 1).end) {
                mergedList.add(interval);
                index++;
            } else {
                mergedList.get(index - 1).end = Math.max(mergedList.get(index - 1).end, interval.end);
            }
        }

        return mergedList.toArray(new Interval[0]);
    }

    static class Interval {
        int start;
        int end;

        public Interval(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
}
